\documentclass{ctexart}
\usepackage[hidelinks]{hyperref}%目录
\usepackage{bookmark}
\usepackage{xeCJK} %导入这个宏包，就可以支持中文
\usepackage{cite}%文献引用
\usepackage{graphicx}
\usepackage{listings}
\usepackage{amsthm,amsmath,amssymb,amsfonts}%数学命题，数学字母，排版
\usepackage[a4paper,left=25.4mm,right=25.4mm,top=29.8mm,bottom=29.8mm]{geometry}

\pagestyle{myheadings}
\numberwithin{equation}{subsection}%以subsection编号equation

%方便打数学公式的新定义
\newcommand{\summ}{\sum\limits}
\newcommand{\limm}{\lim\limits}
\newcommand{\limsupp}{\mathop{\overline{\lim}}\limits}
\newcommand{\liminff}{\mathop{\underline{\lim}}\limits}
\newcommand{\maxx}{\mathop{\max}\limits}
\newcommand{\minn}{\mathop{\min}\limits}
\newcommand{\prodd}{\prod\limits}
\newcommand{\capp}{\bigcap\limits}
\newcommand{\cupp}{\bigcup\limits}
\newcommand{\zupp}{\bigsqcup\limits}
\newcommand{\supp}{\sup\limits}
\newcommand{\inff}{\inf\limits}
\newcommand{\cu}{\mathbf}
\newcommand{\ko}{\mathbb}
\newcommand{\xie}{\mathcal}
\newcommand{\zz}{\mathrm}
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}
\newcommand{\za}{\langle}
\newcommand{\ya}{\rangle}
\newcommand{\zjd}{\left\lvert}
\newcommand{\yjd}{\right\rvert}
\newcommand{\rank}{\zz{rank}}
\newcommand{\nb}{\varPsi}
\newcommand{\cha}{\setminus}



%数学命题环境定义 
%证明环境直接用proof
\theoremstyle{plain} \newtheorem{thm}{定理}[subsection]
\theoremstyle{plain} \newtheorem*{lemma}{引理}
\theoremstyle{plain} \newtheorem*{prop}{prop}
\theoremstyle{plain} \newtheorem*{property}{性质}
\theoremstyle{plain} \newtheorem*{define}{定义}
\theoremstyle{plain} \newtheorem*{cor}{cor}
\theoremstyle{plain} \newtheorem*{eg}{例}
\theoremstyle{plain} \newtheorem{axiom}{公理}
\theoremstyle{remark} \newtheorem*{rmk}{Rmk}
\theoremstyle{plain} \newtheorem*{goal}{Goal}



\title{图的模板类设计}
\author{陈宇涛，3210102287，强基数学2101}


\begin{document}
\maketitle
\tableofcontents

\section{设计思路}
\begin{flushleft}
~\\
~~~~以顶点的名称不定，写成图的类模板形式~\\
template<typename VertexName>~\\
class Graph~\\
Graph 其中必须包含Vertex和Edge.~\\
~\\
~~~~struct Vertex其中最基本应该包含
(1)顶点名称name,(2)在图中的标号 sub\\
(3)为后来其他应用做准备提供它的所有出边vector<Edge>Adj \\
~\\
~~~~struct Edge 中包含最初等的信息,即(1)连接的起点 Vertex st, (2)连接的终点Vertex ed;
(3)边的权重double weight(若无权重,默认为1)\\
\end{flushleft}

\begin{define}
\begin{flushleft}
~\\
称一张图为稀疏图如果$|E|=\Theta(|V|)$\\
称一张图为稠密图如果$|E|=\Theta(|V|^{2})$\\
~\\
当稀疏图时，我们用AdjList的形式更为方便。
所以在设计时只用关注每个顶点的边，需要做的只用依照不同顶点v,找出所有以v为起点的边，然后列出来(u,w,weight)即可
~\\
当图为稠密图，我们用AdjMatrix的形式.
在设计时需要二维数组vector<vector<double>> AdjMatrix里面放每两个顶点之间边的权重A[i][j]即为(i,j,weight)的权重。若为无向图，可以发现矩阵为实对称矩阵。   
\end{flushleft}
\end{define}


\section{测试说明}
\begin{eg}
\begin{flushleft}
~\\
在test.txt写了三个测试样例。bash run后输出。

Input:
\begin{verbatim}
Graph<int>      Graph<char>         Graph<string>
无向有权图      有向有权图          无向无权图    
5 0 1           6 1 1               4 0 0
3 5 6           a b 3               v1 v2 
3 4 1           b c -2              v3 v4
5 6 2           c a 3.4             v4 v2
3 6 1.2         b a -2              v1 v3
4 5 6           a c 4.21
                c b 1
\end{verbatim}



Output:
\begin{lstlisting}
    test1:
The following is all vertexes in this graph 
3 5 4 6
The following is all edges in this graph 
( 3 , 5 , 6 )
( 3 , 4 , 1 )
( 5 , 6 , 2 )
( 3 , 6 , 1.2 )
( 4 , 5 , 6 )

The following is AdjMatrix 
  3 5 4 6 
3 0 6 1 1.2 
5 6 0 6 2 
4 1 6 0 999 
6 1.2 2 999 0 

We choose ADJList by the num of edges and vertexes
The following is AdjList 
3 -> (5 , 6) -> (4 , 1) -> (6 , 1.2) -> NULL
5 -> (5 , 6) -> (6 , 2) -> (5 , 6) -> NULL
4 -> (4 , 1) -> (5 , 6) -> NULL
6 -> (6 , 2) -> (6 , 1.2) -> NULL


    test2:
The following is all vertexes in this graph 
a b c
The following is all edges in this graph 
( a , b , 3 )
( b , c , -2 )
( c , a , 3.4 )
( b , a , -2 )
( a , c , 4.21 )
( c , b , 1 )

The following is AdjList 
a -> (b , 3) -> (c , 4.21) -> NULL
b -> (c , -2) -> (a , -2) -> NULL
c -> (a , 3.4) -> (b , 1) -> NULL

We choose ADJMatrix by the num of edges and vertexes
The following is AdjMatrix 
  a   b  c 
a 0   3  4.21 
b -2  0  -2 
c 3.4 1  0 


test3:
The following is all vertexes in this graph 
v1 v2 v3 v4
The following is all edges in this graph 
( v1 , v2 , 1 )
( v3 , v4 , 1 )
( v4 , v2 , 1 )
( v1 , v3 , 1 )

The following is AdjMatrix 
   v1 v2 v3 v4 
v1 0 1 1 999 
v2 1 0 999 1 
v3 1 999 0 1 
v4 999 1 1 0 

We choose ADJList by the num of edges and vertexes
The following is AdjList 
v1 -> (v2 , 1) -> (v3 , 1) -> NULL
v2 -> (v2 , 1) -> (v2 , 1) -> NULL
v3 -> (v4 , 1) -> (v3 , 1) -> NULL
v4 -> (v4 , 1) -> (v2 , 1) -> NULL

\end{lstlisting}
\end{flushleft}
\end{eg}




\end{document}